{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Connecting Cities With Minimum Cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #graph #minimum-spanning-tree #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #图 #最小生成树 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最低成本联通所有城市"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>想象一下你是个城市基建规划者，地图上有&nbsp;<code>n</code>&nbsp;座城市，它们按以&nbsp;<code>1</code> 到&nbsp;<code>n</code>&nbsp;的次序编号。</p>\n",
    "\n",
    "<p>给你整数 <code>n</code> 和一个数组&nbsp;<code>conections</code>，其中&nbsp;<code>connections[i] = [x<sub>i</sub>, y<sub>i</sub>, cost<sub>i</sub>]</code>&nbsp;表示将城市&nbsp;<code>x<sub>i</sub></code>&nbsp;和城市&nbsp;<code>y<sub>i</sub></code>&nbsp;连接所要的<code>cost<sub>i</sub></code>（<strong>连接是双向的</strong>）。</p>\n",
    "\n",
    "<p>返回连接所有城市的<strong>最低成本</strong>，每对城市之间<strong>至少</strong>有一条路径。如果无法连接所有 <code>n</code>&nbsp;个城市，返回 <code>-1</code></p>\n",
    "\n",
    "<p>该 <strong>最小成本</strong> 应该是所用全部连接成本的总和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/07/27/1314_ex2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/07/27/1314_ex1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, conections = [[1,2,3],[3,4,4]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>即使连通所有的边，也无法连接所有城市。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= connections.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>connections[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt;= n</code></li>\n",
    "\t<li><code>x<sub>i</sub>&nbsp;!= y<sub>i</sub></code></li>\n",
    "\t<li><code>0 &lt;= cost<sub>i</sub>&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [connecting-cities-with-minimum-cost](https://leetcode.cn/problems/connecting-cities-with-minimum-cost/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [connecting-cities-with-minimum-cost](https://leetcode.cn/problems/connecting-cities-with-minimum-cost/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[1,2,5],[1,3,6],[2,3,1]]', '4\\n[[1,2,3],[3,4,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = {}\n",
    "        for i in range(1, n + 1):\n",
    "            graph[i] = []\n",
    "        for x, y, cost in connections:\n",
    "            graph[x].append((y, cost))\n",
    "            graph[y].append((x, cost))\n",
    "\n",
    "        res = 0\n",
    "        mini_heap = [(0, 1)]\n",
    "        visited = set()\n",
    "        while mini_heap:\n",
    "            c, i = heappop(mini_heap)\n",
    "            if i in visited:\n",
    "                continue\n",
    "            else:\n",
    "                visited.add(i)\n",
    "                res += c\n",
    "                if len(visited) == n:\n",
    "                    return res\n",
    "                else:\n",
    "                    for j, c in graph[i]:\n",
    "                        if j in visited:\n",
    "                            continue\n",
    "                        else:\n",
    "                            heappush(mini_heap, (c, j))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.par = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "    def find(self, x):\n",
    "        if x != self.par[x]:\n",
    "            self.par[x] = self.find(self.par[x])\n",
    "        return self.par[x]\n",
    "    def union(self, x, y):\n",
    "        xr, yr = self.find(x), self.find(y)\n",
    "        if xr == yr:\n",
    "            return\n",
    "        if self.size[xr] < self.size[yr]:\n",
    "            xr, yr = yr, xr\n",
    "        self.par[yr] = xr\n",
    "        self.size[xr] += self.size[yr]\n",
    "        \n",
    "class Solution:\n",
    "    def minimumCost(self, N: int, connections: List[List[int]]) -> int:\n",
    "        pairs = sorted(connections, key = lambda x: x[2])\n",
    "        uf = UnionFind(N)\n",
    "        res = 0\n",
    "        for p in pairs:\n",
    "            a, b, c = p[0]-1, p[1]-1, p[2]\n",
    "            if uf.find(a) != uf.find(b):\n",
    "                res += c #only if a and b haven't been in one group, need to add cost.\n",
    "            # if a and b already in one group, just return, which is defined in class UnionFind.\n",
    "            uf.union(a, b)\n",
    "            root = uf.find(a)\n",
    "            if uf.size[root] == N:\n",
    "                return res\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    s = []\n",
    "    def minimumCost(self, N: int, connections: List[List[int]]) -> int:\n",
    "        # 先按照cost排序, 然后添加, 如果根节点相同, 不添加, 根节点不同, 添加, 压缩路径\n",
    "        # 如果node数量到了, 输出\n",
    "        self.s = [-1 for i in range(N)]\n",
    "        connections.sort(key = lambda p: p[2])\n",
    "        ans = 0\n",
    "        while connections:\n",
    "            n1, n2, cost = connections.pop(0)\n",
    "            root1 = self.union_find(n1 - 1)\n",
    "            root2 = self.union_find(n2 - 1)\n",
    "            if root1 == root2:\n",
    "                continue\n",
    "            else:\n",
    "                self.connect(root1, root2)\n",
    "                ans += cost\n",
    "            \n",
    "        cnt = [1 for i in range(N) if self.s[i] < 0]\n",
    "        if sum(cnt) == 1:\n",
    "            return ans  \n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "    # 找到一个节点的根节点\n",
    "    def union_find(self, x):\n",
    "        # 如果是-1, 就表明本身是根节点, 返回\n",
    "        if self.s[x] < 0:\n",
    "            return x\n",
    "        else:\n",
    "            self.s[x] = self.union_find(self.s[x])\n",
    "            return self.s[x]\n",
    "\n",
    "    # 链接两个节点\n",
    "    def connect(self, r1, r2):\n",
    "        little = r1\n",
    "        large = r2\n",
    "        \n",
    "        size = self.s[r1] + self.s[r2]\n",
    "\n",
    "        if r1 < r2:\n",
    "            little = r2\n",
    "            large = r1\n",
    "        \n",
    "        self.s[little] = large\n",
    "        self.s[large] = size\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumCost(self, N: int, connections: List[List[int]]) -> int:\n",
    "        # 先按照cost排序, 然后添加, 如果根节点相同, 不添加, 根节点不同, 添加, 压缩路径\n",
    "        # 如果node数量到了, 输出\n",
    "        self.s = [-1 for i in range(N)]\n",
    "        connections.sort(key = lambda p: p[2])\n",
    "        ans = 0\n",
    "        while connections:\n",
    "            n1, n2, cost = connections.pop(0)\n",
    "            root1 = self.find(n1 - 1)\n",
    "            root2 = self.find(n2 - 1)\n",
    "            if root1 == root2:\n",
    "                continue\n",
    "            else:\n",
    "                self.union(root1, root2)\n",
    "                ans += cost\n",
    "            \n",
    "        cnt = [1 for i in range(N) if self.s[i] < 0]\n",
    "        if sum(cnt) == 1:\n",
    "            return ans  \n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "    # 找到一个节点的根节点\n",
    "    def find(self, x):\n",
    "        # 如果是-1, 就表明本身是根节点, 返回\n",
    "        if self.s[x] < 0:\n",
    "            return x\n",
    "        else:\n",
    "            # 压缩节点\n",
    "            self.s[x] = self.find(self.s[x])\n",
    "            return self.s[x]\n",
    "\n",
    "    # 链接两个节点\n",
    "    def union(self, r1, r2):\n",
    "        self.s[r1] = r2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1 for i in range(n)]\n",
    "        self.cnt = 0\n",
    "\n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx != ry:\n",
    "            self.cnt += 1\n",
    "            sx, sy = self.size[rx], self.size[ry]\n",
    "            if sx > sy:\n",
    "                self.parent[ry] = rx\n",
    "            else:\n",
    "                self.parent[rx] = ry\n",
    "                if sy == sx:\n",
    "                    self.size[ry] += 1\n",
    "    \n",
    "    def is_connect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        u_s = UnionSet(n)\n",
    "        connections.sort(key=lambda x:x[2], reverse=True)\n",
    "        ans = 0\n",
    "        while u_s.cnt < n and connections:\n",
    "            x, y, p = connections.pop()\n",
    "            if not u_s.is_connect(x-1, y-1):\n",
    "                u_s.union(x-1, y-1)\n",
    "                ans += p\n",
    "        return ans if u_s.is_connect(0, n-1) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class union:\n",
    "    def __init__ (self,n):\n",
    "        self.father=[i for i in range(n)]\n",
    "        self.size=[1]*n\n",
    "        self.part=n\n",
    "    def find(self,x):\n",
    "        if self.father[x]!=x:\n",
    "            root=self.find(self.father[x])\n",
    "            self.father[x]=root\n",
    "            return root\n",
    "        return x\n",
    "    def merge(self,x,y):\n",
    "        root_x=self.find(x)\n",
    "        root_y=self.find(y)\n",
    "        if root_x!=root_y:\n",
    "            if self.size[x]<self.size[y]:\n",
    "                root_x,root_y=root_y,root_x\n",
    "            self.father[root_y]=root_x\n",
    "            self.size[x]+=self.size[y]\n",
    "            self.size[y]=0\n",
    "            self.part-=1\n",
    "\n",
    "    def is_connect(self,x,y):\n",
    "        return self.find(x)==self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        r=len(connections)\n",
    "        c=len(connections[0])\n",
    "        connections.sort(key=lambda x : x[2])\n",
    "        u=union(n)\n",
    "        res=0\n",
    "        while connections:\n",
    "            x,y,cost=connections.pop(0)\n",
    "            if not u.is_connect(x-1,y-1) and u.part>1:\n",
    "                u.merge(x-1,y-1)\n",
    "                res+=cost\n",
    "            if u.part==1:\n",
    "                return res\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "        def __init__(self, n):\n",
    "            self.parent = {\n",
    "                i: i\n",
    "                for i in range(1, n+1)\n",
    "            }\n",
    "            self.count = n\n",
    "\n",
    "        def is_connected(self, a, b):\n",
    "            return self.find(a) == self.find(b)\n",
    "        \n",
    "        def find(self, x):\n",
    "            if self.parent[x] == x:\n",
    "                return x\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            return self.parent[x]\n",
    "\n",
    "        def union(self, a, b):\n",
    "            a_parent = self.find(a)\n",
    "            b_parent = self.find(b)\n",
    "            if a_parent != b_parent:\n",
    "                self.parent[b_parent] = a_parent\n",
    "                self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        connections.sort(key=lambda e: e[2], reverse=True)\n",
    "        uf = UF(n)\n",
    "\n",
    "        total_cost = 0\n",
    "        while connections:\n",
    "            u, v, weight = connections.pop()\n",
    "            if not uf.is_connected(u, v):\n",
    "                uf.union(u, v)\n",
    "                total_cost += weight\n",
    "        \n",
    "        if uf.count == 1:\n",
    "            return total_cost\n",
    "        return -1\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        connections.sort(key = lambda x:-x[2])\n",
    "        root = [i for i in range(n)]\n",
    "        ans = 0\n",
    "        for _ in range(n-1):\n",
    "            if not connections: return -1 \n",
    "            while 1:\n",
    "                x, y, cost = connections.pop()\n",
    "                x-=1; y-=1\n",
    "                while root[x] != root[root[x]]: root[x] = root[root[x]]\n",
    "                while root[y] != root[root[y]]: root[y] = root[root[y]]\n",
    "                if root[x] != root[y]:  \n",
    "                    root[root[x]] = root[y]\n",
    "                    ans += cost\n",
    "                    break \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        fa = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            fa[i] = i\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "        connections.sort(key = lambda x : x[2])\n",
    "        cnt = ans = 0\n",
    "        for x, y, c in connections:\n",
    "            px, py = find(x - 1), find(y - 1)\n",
    "            if px != py:\n",
    "                cnt += 1\n",
    "                ans += c\n",
    "                if cnt == n - 1:\n",
    "                    return ans\n",
    "                fa[px] = py\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue \n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # # 建图\n",
    "        # nodedict = {}\n",
    "        # for i in range(1,n+1):\n",
    "        #     nodedict[i] = []\n",
    "        # for i,j,value in connections:\n",
    "        #     nodedict[i].append([value,j])\n",
    "        #     # 双向的\n",
    "        #     nodedict[j].append([value,i])\n",
    "        # kruskal算法\n",
    "\n",
    "        def find(x): # 并查集\n",
    "            if x == father[x]:\n",
    "                return x\n",
    "            return find(father[x])\n",
    "        \n",
    "        father = [i for i in range(n+1)]\n",
    "        connections.sort(key=lambda x: x[2])\n",
    "        res = 0\n",
    "        edge_cnt = 0\n",
    "        while(connections):\n",
    "            i,j,value = connections.pop(0)\n",
    "            fatheri = find(i)\n",
    "            fatherj = find(j)\n",
    "            if fatheri != fatherj:\n",
    "                father[fatheri] = fatherj\n",
    "                res += value\n",
    "                edge_cnt += 1\n",
    "            if edge_cnt == n - 1:\n",
    "                return res\n",
    "\n",
    "        return -1\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        # # Prim\n",
    "        # edges = PriorityQueue()\n",
    "        # nodeset = set()\n",
    "        # nodeset.add(1)\n",
    "        # for i in nodedict[1]:\n",
    "        #     edges.put(i)\n",
    "        \n",
    "        # res = 0\n",
    "        # # 注意优先级队列的判定空不一样\n",
    "        # while(not edges.empty() and len(nodeset) != n):\n",
    "        #     value,i = edges.get()\n",
    "        #     if i in nodeset:\n",
    "        #         continue\n",
    "        #     nodeset.add(i)\n",
    "        #     res += value\n",
    "        #     for j in nodedict[i]:\n",
    "        #         edges.put(j)\n",
    "        \n",
    "        # if len(nodeset) == n:\n",
    "        #     return res\n",
    "        # else:\n",
    "        #     return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(a, b):\n",
    "            x, y = find(a), find(b)\n",
    "            if x == y:\n",
    "                return\n",
    "            p[x] = y\n",
    "        p = list(range(n+1))\n",
    "        edges.sort(key = lambda x : x[-1])\n",
    "        ans = 0\n",
    "        for x, y, v in edges:\n",
    "            if find(x) == find(y):\n",
    "                continue\n",
    "            merge(x, y)\n",
    "            ans += v\n",
    "            n -= 1\n",
    "        if n == 1:\n",
    "            return ans\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "        # 新增一个数组记录树的“重量”\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def union(self, p: int, q: int) -> None:\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        if rootP == rootQ:\n",
    "            return\n",
    "\n",
    "        # 小树接到大树下面，较平衡\n",
    "        if self.size[rootP] > self.size[rootQ]:\n",
    "            self.parent[rootQ] = rootP\n",
    "            self.size[rootP] += self.size[rootQ]\n",
    "        else:\n",
    "            self.parent[rootP] = rootQ\n",
    "            self.size[rootQ] += self.size[rootP]\n",
    "        self.count -= 1\n",
    "\n",
    "    def connected(self, p: int, q: int) -> bool:\n",
    "        root_p = self.find(p)\n",
    "        root_q = self.find(q)\n",
    "        return root_p == root_q\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        while self.parent[x] != x:\n",
    "            # 这行代码进行路径压缩\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def count(self) -> int:\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        uf  = UF(n+1)\n",
    "        re = 0\n",
    "        new_connection = sorted(connections,key=lambda x:x[2])\n",
    "        for i in new_connection:\n",
    "            point1 = i[0]\n",
    "            point2 = i[1]\n",
    "            weight = i[2]\n",
    "            if uf.connected(point1,point2):\n",
    "                continue\n",
    "            re+=weight\n",
    "            uf.union(point1, point2)\n",
    "\n",
    "        if uf.count==2:\n",
    "            return re\n",
    "        else:\n",
    "            return -1\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "        self.part = n\n",
    "    #------- 扁平化\n",
    "    def Find(self, x) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.Find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    #---------- size策略\n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, N: int, connections: List[List[int]]) -> int:\n",
    "        #--------------------- kruskal算法\n",
    "        edge = [(cost, x-1, y-1) for x,y,cost in connections]\n",
    "        edge.sort()\n",
    "\n",
    "        tot_cost = 0\n",
    "        MST = UnionFind(N)\n",
    "        for cost, x, y in edge:\n",
    "            if MST.Union(x, y) == False:\n",
    "                continue\n",
    "            tot_cost += cost\n",
    "            if MST.part == 1:\n",
    "                return tot_cost\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        parent = list(range(n+1))\n",
    "        def find(i: int) -> int:\n",
    "            if parent[i] != i:\n",
    "                parent[i] = find(parent[i])\n",
    "            return parent[i]\n",
    "\n",
    "        def union(i: int, j: int):\n",
    "            parent[find(i)] = find(j)\n",
    "\n",
    "        def takethird(elem):\n",
    "            return elem[2]\n",
    "        connections.sort(key=takethird)\n",
    "\n",
    "        route = 0\n",
    "        for path in connections:\n",
    "            if find(path[0]) != find(path[1]):\n",
    "                union(path[0], path[1])\n",
    "                route += path[2]\n",
    "        root = [i for i in range(len(parent))if i == parent[i]]\n",
    "        return route if len(root) == 2 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, x):\n",
    "        if x == self.father[x]:\n",
    "            return x\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        self.father = [i for i in range(n+1)]\n",
    "        connections.sort(key = lambda x: x[2])\n",
    "        ans = 0\n",
    "        edge_cnt = 0\n",
    "\n",
    "        for a, b , cost in connections:\n",
    "            root_a = self.find(a)\n",
    "            root_b = self.find(b)\n",
    "            if root_a != root_b:\n",
    "                self.father[root_a] = root_b\n",
    "                ans += cost\n",
    "                edge_cnt += 1\n",
    "            if edge_cnt == n - 1:\n",
    "                return ans \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union_find:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.count = n\n",
    "    \n",
    "    def find(self, a):\n",
    "        while a != self.parent[a]:\n",
    "            self.parent[a] = self.parent[self.parent[a]]\n",
    "            a = self.parent[a]\n",
    "        return a\n",
    "    \n",
    "    def union(self, a, b):\n",
    "        pa = self.find(a)\n",
    "        pb = self.find(b)\n",
    "        if pa == pb:\n",
    "            return\n",
    "        \n",
    "        if self.size[pa] < self.size[pb]:\n",
    "            self.parent[pa] = pb\n",
    "            self.size[pb] += self.size[pa]\n",
    "        else:\n",
    "            self.parent[pb] = pa\n",
    "            self.size[pa] += self.size[pb]\n",
    "        self.count -= 1\n",
    "    \n",
    "    def connect(self, a, b):\n",
    "        return self.find(a) == self.find(b)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        uf = Union_find(n + 1)\n",
    "        connections.sort(key=lambda x: x[2])\n",
    "        cost = 0\n",
    "        for c in connections:\n",
    "            if not uf.connect(c[0], c[1]):\n",
    "                cost += c[2]\n",
    "                uf.union(c[0], c[1])\n",
    "        return -1 if uf.count != 2 else cost\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        par=[i for i in range(n+1)]\n",
    "        connections.sort(key=lambda k:k[2])\n",
    "        size=[1 for i in range(n+1)]\n",
    "        part=n\n",
    "        ans=0\n",
    "        def find(x):\n",
    "            if par[x]==x:\n",
    "                return x\n",
    "            return find(par[x])\n",
    "        def un(x,y):\n",
    "            rtx,rty=find(x),find(y)\n",
    "            if size[rtx]<size[rty]:\n",
    "                rtx,rty=rty,rtx\n",
    "            if rtx==rty:\n",
    "                return False\n",
    "            par[rty]=rtx\n",
    "            nonlocal part\n",
    "            part-=1\n",
    "            size[rtx]+=1\n",
    "            return True\n",
    "        def isc(x,y):\n",
    "            return find(x)==find(y)\n",
    "        for x,y,w in connections:\n",
    "            if not isc(x,y):\n",
    "                un(x,y)\n",
    "                ans+=w\n",
    "            if part==1:\n",
    "                return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # 本质上是最小生成树的问题\n",
    "        # 思路是，升序排序cost，升序遍历边，依次判断这个边是否在连通图中，如果不在，就加入到连同图里，直到最后所有节点都在联通图上\n",
    "        uf = UF(n+1) # 0号位没用\n",
    "        connections = sorted(connections, key=lambda c:c[2])\n",
    "        all_cost = 0\n",
    "        for c in connections:\n",
    "            if not uf.connected(c[0], c[1]):\n",
    "                uf.union(c[0], c[1])\n",
    "                all_cost += c[2]\n",
    "        \n",
    "        if uf.count != 2:\n",
    "            return -1\n",
    "        else:\n",
    "            return all_cost\n",
    "\n",
    "\n",
    "class UF:\n",
    "    # n 为图中节点的个数\n",
    "    def __init__(self, n: int):\n",
    "        self.count = n\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "    # 将节点 p 和节点 q 连通\n",
    "    def union(self, p: int, q: int):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        if rootP == rootQ:\n",
    "            return\n",
    "\n",
    "        self.parent[rootQ] = rootP\n",
    "        # 两个连通分量合并成一个连通分量\n",
    "        self.count -= 1\n",
    "\n",
    "    # 判断节点 p 和节点 q 是否连通\n",
    "    def connected(self, p: int, q: int) -> bool:\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "        return rootP == rootQ\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    # 返回图中的连通分量个数\n",
    "    def count(self) -> int:\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        par=[i for i in range(n+1)]\n",
    "        connections.sort(key=lambda k:k[2])\n",
    "        part=n\n",
    "        ans=0\n",
    "        def find(x):\n",
    "            if par[x]==x:\n",
    "                return x\n",
    "            return find(par[x])\n",
    "        def un(x,y):\n",
    "            rtx,rty=find(x),find(y)\n",
    "            if rtx==rty:\n",
    "                return False\n",
    "            par[rty]=rtx\n",
    "            nonlocal part\n",
    "            part-=1\n",
    "            return True\n",
    "        def isc(x,y):\n",
    "            return find(x)==find(y)\n",
    "        for x,y,w in connections:\n",
    "            if not isc(x,y):\n",
    "                un(x,y)\n",
    "                ans+=w\n",
    "            if part==1:\n",
    "                return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edges = [[] for i in range(n + 1)]\n",
    "        for a, b, cost in connections:\n",
    "            edges[a].append((b, cost))\n",
    "            edges[b].append((a, cost))\n",
    "        \n",
    "        intree = set()\n",
    "        heap = [(0, 1)]\n",
    "        ans = 0\n",
    "        while heap and len(intree) != n:\n",
    "            cost, city = heapq.heappop(heap)\n",
    "            if city not in intree:\n",
    "                intree.add(city)\n",
    "                ans += cost\n",
    "                for next_city, next_cost in edges[city]:\n",
    "                    heapq.heappush(heap, (next_cost, next_city))\n",
    "        if len(intree) == n:\n",
    "            return ans\n",
    "        return -1\n",
    "                    \n",
    "                    \n",
    "                \n",
    "            \n",
    "        \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # n = len(graph)  # 图的顶点数\n",
    "        visited = [False] * n  # 记录顶点是否已经加入生成树\n",
    "        min_heap = [(0, 0)]  # 优先队列，用于选择最小权值的边\n",
    "        total_cost = 0  # 记录生成树的总权值\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y,w in connections:\n",
    "            g[x-1].append((y-1,w))\n",
    "            g[y-1].append((x-1,w))\n",
    "\n",
    "        while min_heap:\n",
    "            cost, node = heapq.heappop(min_heap)\n",
    "            if visited[node]:\n",
    "                continue\n",
    "            visited[node] = True\n",
    "            total_cost += cost\n",
    "\n",
    "            for neighbor, edge_cost in g[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    heapq.heappush(min_heap, (edge_cost, neighbor))\n",
    "        if visited.count(False) >0:\n",
    "            return -1\n",
    "        return total_cost\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def build_graph(n: int, connections: List[List[int]]) -> Optional[List[List[int]]]:\n",
    "    if not connections:\n",
    "        return\n",
    "    graph = [[] for _ in range(n)]\n",
    "    for edge in connections:\n",
    "        u, v = edge[0] - 1, edge[1] - 1\n",
    "        weight = edge[2]\n",
    "        graph[u].append([weight, u, v])\n",
    "        graph[v].append([weight, v, u])\n",
    "    return graph\n",
    "\n",
    "\n",
    "class Prim:\n",
    "    def __init__(self, graph: List[List[int]]):\n",
    "        self.graph = graph\n",
    "        self.in_mst = [False] * len(graph)\n",
    "        self.weight_sum = 0\n",
    "        self.priority_queue = []\n",
    "\n",
    "        self.cut(0)\n",
    "        self.in_mst[0] = True\n",
    "        while self.priority_queue:\n",
    "            edge = heapq.heappop(self.priority_queue)\n",
    "            to = edge[2]\n",
    "            weight = edge[0]\n",
    "            if self.in_mst[to]:\n",
    "                continue\n",
    "            self.weight_sum += weight\n",
    "            self.in_mst[to] = True\n",
    "            self.cut(to)\n",
    "\n",
    "    def cut(self, v: int) -> None:\n",
    "        for edge in self.graph[v]:\n",
    "            to = edge[2]\n",
    "            if self.in_mst[to]:\n",
    "                continue\n",
    "            heapq.heappush(self.priority_queue, edge)\n",
    "\n",
    "    def all_connected(self) -> bool:\n",
    "        for i in range(len(self.in_mst)):\n",
    "            if not self.in_mst[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = build_graph(n, connections)\n",
    "        prim = Prim(graph)\n",
    "        if not prim.all_connected():\n",
    "            return -1\n",
    "        return prim.weight_sum\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #解题思路：\n",
    "        #求最小生成树\n",
    "        #prim算法\n",
    "\n",
    "        edges = [[] for i in range(n + 1)]\n",
    "        for a,b,cost in connections:\n",
    "            edges[a].append((cost,b))\n",
    "            edges[b].append((cost,a))\n",
    "        \n",
    "        visited = set()\n",
    "        out_edges = [(0,1)] #从顶点1开始\n",
    "        res = 0\n",
    "        while out_edges and len(visited) <= n:\n",
    "            cost,city = heapq.heappop(out_edges)\n",
    "            if city not in visited:\n",
    "                visited.add(city)\n",
    "                res += cost\n",
    "                for next_cost,next_city in edges[city]:\n",
    "                    heapq.heappush(out_edges,(next_cost,next_city))\n",
    "        return res if len(visited) == n else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
